package problems.daily.y2021m6;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author habitplus
 * @since 2021-06-22 09:18
 */
public class T20210622N1 {
    /**
     * 剑指 Offer 38. 字符串的排列
     * 输入一个字符串，打印出该字符串中字符的所有排列。
     * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
     */
    private Set<String> set = new HashSet<>();
    private boolean[] visited;
    public String[] permutation(String s) {
        if (s != null && !"".equals(s)) {
            int len = s.length();
            visited = new boolean[len];
            // 回溯
            backtrack(s, len, new StringBuilder());
        }
        return set.toArray(new String[0]);
    }

    private void backtrack(String sourceStr, int len, StringBuilder tmpSb) {
        if (tmpSb.length() == len) {
            // 得到一个字符串
            set.add(tmpSb.toString());
            return;
        }

        for (int i = 0; i < len; i++) {
            if (!visited[i]) {
                visited[i] = true;
                tmpSb.append(sourceStr.charAt(i));
                backtrack(sourceStr, len, tmpSb);
                visited[i] = false;
                tmpSb.deleteCharAt(tmpSb.length() - 1);
            }
        }
    }

    public void backtrack01(char[] arr, int i, int n, StringBuilder perm) {
        if (i == n) {
            set.add(perm.toString());
            return;
        }

        for (int j = 0; j < n; j++) {
            /*
                保证在填每一个空位的时候重复字符只会被填入一次。
                具体地，我们首先对原字符串排序，保证相同的字符都相邻，
                在递归函数中，我们限制每次填入的字符一定是这个字符所在重复字符集合中「从左往右第一个未被填入的字符」
            */
            if (visited[j] || (j > 0 && !visited[j - 1] && arr[j - 1] == arr[j])) {
                continue;
            }
            visited[j] = true;
            perm.append(arr[j]);
            backtrack01(arr, i + 1, n, perm);
            perm.deleteCharAt(perm.length() - 1);
            visited[j] = false;
        }
    }

    public static void main(String[] args) {
        T20210622N1 test = new T20210622N1();
        System.out.println(Arrays.toString(test.permutation("abcc")));
    }

}
